1. Field of the Invention
The invention relates generally to data streams and more specifically relates to correcting errors in data streams coded with a line code and an error detection scheme.
2. Discussion of Related Art
Certain data streams, especially high speed data streams including those of a storage system, are often transmitted without an accompanying clock signal. Instead, a receiver generates a clock based on transitions in a data stream. In order for the receiver to generate the clock, the data stream must include sufficient transitions. To ensure there are sufficient transitions, the serial data stream is often encoded into a line code that is chosen for transmission purposes. For example, a line code chosen for a Serial Attached Small Computer System Interface (“SAS”) data stream is the 8B10B coding scheme. Many details of the SAS family of standards may be found at www.t10.org.
The 8B10B coding scheme provides that each 8-bit data byte is encoded into a 10-bit character. The 10-bit character is transmitted instead of the 8-bit data byte. Because not all 10-bit combinations are used to represent all possible 8-bit data bytes, some 10-bit combinations are invalid 8B10B characters. A valid 8B10B character can include five 0's and five 1's, four 0's and six 1's, or six 0's and four 1's. Each 8-bit data byte is encoded into one of two 10-bit 8B10B characters; one character is transmitted when the running disparity is positive and another character is transmitted when the running disparity is negative.
A positive running disparity roughly means that one more 1's have been transmitted than the number of transmitted 0's, and a negative running disparity roughly means that one more 0's have been transmitted than the number of transmitted 1's. Running disparity is a concept used in the 8B10B coding scheme to keep the number of transmitted 0's and 1's roughly equal; the running disparity may be changed depending on the 8B10B character (or subblocks of the character) that is transmitted. For example, if the running disparity is already positive (i.e., roughly one more 1's have been transmitted than 0's), a character (or subblocks of the character) cannot cause the running disparity to further become positive (i.e., causing the number of transmitted 0's and 1's to become even more unequal). Instead, the character needs to either maintain the running disparity as positive (i.e., roughly one more 1's remains to have been transmitted than 0's), or cause the running disparity to become negative (roughly one more 0's have been transmitted than 1's).
Meanwhile, transmission of the serial data stream inevitably results in bit errors. Although information relating to the 8B10B coding scheme may be used to detect certain errors in encoded 10-bit 8B10B characters, a scheme designed specifically to detect data errors is often used. Additionally, the data stream may be arranged as a series of data frames, and the data detection scheme is applied to each data frame. For example, a SAS data frame includes a cyclic redundancy check (“CRC”) value to help detect errors in decoded 8-bit data bytes of a data frame. The CRC value is a result of a computation that resembles a long division operation on the data frame.
As data streams are being transmitted at high speeds, there is a corresponding high likelihood for encountering data errors. For example, even if a single-bit error is only expected for every trillion bits that are transmitted, at a transmission speed of three gigabits per second, a bit error is expected in less than ten minutes. The transmission error is typically reported to a host computer and becomes observable by a user. The host computer would typically attempt to correct the error through retransmission, but it slows down the overall transmission speed. The transmission error, although usually correctable after the retransmission, also causes some users to think the system is unreliable even though the error should be expected given the high transmission speed. These issues become even more critical as speed increases—such as SAS soon adopting 12 gigabits per second speed.
Thus it is an ongoing challenge to reduce the number of errors that need to be reported to the host computer in communication using line coding including 8B10B.